#include<iostream>
#include<vector>
#include<assert.h>
#include<unordered_map>
using namespace std;
template<class T, class Compare>
class HeapGreater
{
public:
    HeapGreater()
        :heapSize(0)
    {}
    ~HeapGreater()
    {
        heapSize = 0;
        heap.clear();
    }
    template<class InputIterator>
    HeapGreater(InputIterator first, InputIterator last)
    {
        while (first != last)
        {
            push(*first);
            first++;
        }
    }
    void push(const T& val)
    {
        heap.push_back(val);
        indexMap[val] = heapSize;
        AdjustUp(heapSize);
        heapSize++;
    }
    void pop()
    {
        assert(!empty());
        T& top = heap[0];
        Swap(0, heapSize - 1);
        heapSize--;
        heap.pop_back();
        indexMap.erase(top);
        AdjustDown(0);
    }
    void set(const T& obj, const T& target)
    {
        int index = indexMap[obj];
        heap[index] = target;
        indexMap[target] = index;
        indexMap.erase(obj);
        resign(target);
    }
    void erase(const T& obj)
    {
        T& tail = heap[heapSize-1];
        int index = indexMap[obj];
        indexMap.erase(obj);
        heapSize--;
        if (obj != tail)
        {
            indexMap[tail] = index;
            heap[index] = tail;
            resign(tail);
        }
        heap.pop_back();
    }
    T& top()
    {
        assert(!empty());
        return heap[0];
    }
    bool empty()
    {
        return heapSize == 0;
    }
    size_t size()
    {
        return heapSize;
    }
private:
    void Swap(int i, int j)
    {
        //根据下标得到值
        T t1 = heap[i];
        T t2 = heap[j];
        //值交换
        heap[i] = t2;
        heap[j] = t1;
        //映射交换
        indexMap[t1] = j;
        indexMap[t2] = i;
    }
    void resign(const T& obj)
    {
        int index = indexMap[obj];
        AdjustDown(index);
        AdjustUp(index);
    }
    void AdjustDown(int parent) //向下调整
    {
        int child = parent * 2 + 1;
        while (child < heapSize)
        {
            if (child + 1 < heapSize && _cmp(heap[child],heap[child+1]))
                child += 1;
            if (_cmp(heap[parent], heap[child]))
            {
                Swap(parent, child);
                parent = child;
                child = parent * 2 + 1;
            }
            else
            {
                break;
            }
        }
    }
    void AdjustUp(int child)//向上调整
    {
        int parent = (child - 1) / 2;
        while (child > 0)
        {
            if (_cmp(heap[parent], heap[child]))
            {
                Swap(child, parent);
                child = parent;
                parent = (child - 1) / 2;
            }
            else
            {
                break;
            }
        }
    }
private:
    unordered_map<T, int> indexMap;//反向索引表 元素-下标
    vector<T> heap;
    int heapSize = 0;
    Compare _cmp;
};